home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / Other Langs / Tickle-4.0 (tcl) / tcl / extend / src / tclXregexp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-11-05  |  16.9 KB  |  521 lines  |  [TEXT/MPS ]
  1. /*
  2.  * tclXregexp.c --
  3.  *
  4.  * Tcl regular expression pattern matching utilities.
  5.  *-----------------------------------------------------------------------------
  6.  * Copyright 1991-1993 Karl Lehenbauer and Mark Diekhans.
  7.  *
  8.  * Permission to use, copy, modify, and distribute this software and its
  9.  * documentation for any purpose and without fee is hereby granted, provided
  10.  * that the above copyright notice appear in all copies.  Karl Lehenbauer and
  11.  * Mark Diekhans make no representations about the suitability of this
  12.  * software for any purpose.  It is provided "as is" without express or
  13.  * implied warranty.
  14.  *-----------------------------------------------------------------------------
  15.  * Boyer-Moore code from: 
  16.  *     torek-boyer-moore/27-Aug-90 by
  17.  *     chris@mimsy.umd.edu (Chris Torek)
  18.  *-----------------------------------------------------------------------------
  19.  * $Id: tclXregexp.c,v 2.7 1993/08/31 23:03:20 markd Exp $
  20.  *-----------------------------------------------------------------------------
  21.  */
  22.  
  23. #include "tclExtdInt.h"
  24. #ifndef macintosh
  25. #    include "regexp.h"
  26. #endif
  27.  
  28. /*
  29.  * This is declared in tclUtil.c.  Must be set to NULL before compiling
  30.  * a regular expressions.
  31.  */
  32. extern char *tclRegexpError;
  33.  
  34. /*
  35.  * Meta-characters for regular expression
  36.  */
  37. #define REXP_META                   "^$.[()|?+*\\"
  38. #define REXP_META_NO_BRACKET_NO_OR  "^$.()?+*\\"
  39.  
  40. #ifndef CHAR_MAX
  41. #    define CHAR_MAX 255
  42. #endif
  43.  
  44. /*
  45.  * Prototypes of internal functions.
  46.  */
  47.  
  48. static char *
  49. BoyerMooreCompile _ANSI_ARGS_((char *pat,
  50.                                   int patlen));
  51.  
  52. static char *
  53. BoyerMooreExecute _ANSI_ARGS_((char     *text,
  54.                                unsigned  textlen,
  55.                                char     *compPtr,
  56.                                unsigned *patLenP));
  57.  
  58. static int
  59. FindNonRegExpSubStr _ANSI_ARGS_((char  *expression,
  60.                                  char **subStrPtrPtr));
  61.  
  62.  
  63. /*
  64.  * Boyer-Moore search: input is `text' (a string) and its length,
  65.  * and a `pattern' (another string) and its length.
  66.  *
  67.  * The linear setup cost of this function is approximately 256 + patlen.
  68.  * Afterwards, however, the average cost is O(textlen/patlen), and the
  69.  * worst case is O(textlen+patlen).
  70.  *
  71.  * The Boyer-Moore algorithm works by observing that, for each position
  72.  * in the text, if the character there does *not* occur somewhere in the
  73.  * search pattern, no comparisons including that character will match.
  74.  * That is, given the text "hello world..." and the pattern "goodbye", the
  75.  * `w' in `world' means that none of `hello w', `ello wo', `llo wor',
  76.  * `lo worl', `o world', ` world.', and `world..' can match.  In fact,
  77.  * exactly patlen strings are certain not to match.  We can discover this
  78.  * simply by looking at the patlen'th character.  Furthermore, even if
  79.  * the text character does occur, it may be that it rules out some number
  80.  * of other matches.  Again, we can discover this by doing the match
  81.  * `backwards'.
  82.  *
  83.  * We set up a table of deltas for each possible character, with
  84.  * delta[character] being patlen for characters not in the pattern,
  85.  * less for characters in the pattern, growing progressively smaller
  86.  * as we near the end of the pattern.  Matching then works as follows:
  87.  *
  88.  *       0         1         2         3
  89.  *       01234567890123456789012345678901234567
  90.  *      "Here is the string being searched into"        (text)
  91.  *       ------                                         (pos = [0..5])
  92.  *      "string"                                        (pat)
  93.  *      654321-                                         (deltas)
  94.  *
  95.  * (the delta for `-' will be derived below).
  96.  *
  97.  * Positions 0..5 end with `i', which is not the `g' we want.  `i' does
  98.  * appear in `string', but two characters before the end.  We skip
  99.  * forward so as to make the `i's match up:
  100.  *
  101.  *      "Here is the string being searched into"        (text)
  102.  *        "string"                                      (pos = [2..7])
  103.  *
  104.  * Next we find that ` ' and `g' do not match.  Since ` ' does not appear
  105.  * in the pattern at all, we can skip forward 6:
  106.  *
  107.  *      "Here is the string being searched into"        (text)
  108.  *              "string"                                (pos = [8..13])
  109.  *
  110.  * Comparing `t' vs `g', we again find no match, and so we obtain the
  111.  * delta for `t', which is 4.  We skip to position 17:
  112.  *
  113.  *      "Here is the string being searched into"        (text)
  114.  *                  "string"                            (pos = [12..17])
  115.  *
  116.  * It thus takes only four steps to move the search point forward to the
  117.  * match, in this case.
  118.  *
  119.  * If the pattern has a recurring character, we must set the delta for
  120.  * that character to the distance of the one closest to the end:
  121.  *
  122.  *      "befuddle the cat"      (text)
  123.  *      "fuddle"                (pos = [0..5])
  124.  *      654321-                 (delta)
  125.  *
  126.  * We want the next search to line the `d's up like this:
  127.  *
  128.  *      "befuddle the cat"      (text)
  129.  *        "fuddle"              (pos = [2..7])
  130.  *
  131.  * and not like this:
  132.  *
  133.  *      "befuddle the cat"      (text)
  134.  *         "fuddle"             (pos = [3..8])
  135.  *
  136.  * so we take the smaller delta for d, i.e., 2.
  137.  *
  138.  * The last task is computing the delta we have noted above as `-':
  139.  *
  140.  *      "candlesticks"          (text)
  141.  *      "hand"                  (pos = [0..3])
  142.  *      4321-                   (delta)
  143.  *
  144.  * Here the `d' in `hand' matches the `d' in `candlesticks', but the
  145.  * strings differ.  Since there are no other `d's in `hand', we know
  146.  * that none of (cand,andl,ndle,dles) can match, and thus we want this
  147.  * delta to be 4 (the length of the pattern).  But if we had, e.g.:
  148.  *
  149.  *      "candlesticks"          (text)
  150.  *      "deed"                  (pos = [0..3])
  151.  *      4321-                   (delta)
  152.  *
  153.  * then we should advance to line up the other `d':
  154.  *
  155.  *      "candlesticks"          (text)
  156.  *         "deed"               (pos = [3..6])
  157.  *
  158.  * As this suggests, the delta should be that for the `d' nearest the
  159.  * end, but not including the end.  This is easily managed by setting up
  160.  * a delta table as follows:
  161.  *
  162.  *      for int:c in [0..255] { delta[c] = patlen; };
  163.  *      for int:x in [0..patlen-1) { delta[pat[x]] = patlen - (x + 1); };
  164.  *
  165.  * delta[pat[patlen-1]] is never written, so the last letter inherits the
  166.  * delta from an earlier iteration or from the previous loop.
  167.  *
  168.  * NB: the nonsense with `deltaspace' below exists merely because gcc
  169.  * does a horrible job of common subexpression elimination (it does not
  170.  * notice that the array is at a constant stack address).
  171.  */
  172.  
  173. struct compiled_search_struct {
  174.         unsigned patlen;
  175.         unsigned deltaspace[CHAR_MAX + 1];
  176. };
  177.  
  178.  
  179. static char *
  180. BoyerMooreCompile (pat, patlen)
  181.     char *pat;
  182.     int   patlen;
  183. {
  184.         register unsigned char *p, *t;
  185.         register unsigned i, p1, j, *delta;
  186.         struct compiled_search_struct *cp;
  187.         int alloc_len;
  188.  
  189.         /*
  190.          * Algorithm fails if pattern is empty.
  191.          */
  192.         if ((p1 = patlen) == 0)
  193.                 return (NULL);
  194.  
  195.         alloc_len = sizeof(struct compiled_search_struct) + patlen + 1;
  196.         cp = (struct compiled_search_struct *) ckalloc (alloc_len);
  197.  
  198.         strncpy((char *)cp+sizeof(struct compiled_search_struct), pat, patlen);
  199.         *((char *)cp+alloc_len-1) = '\0';
  200.  
  201.         /* set up deltas */
  202.         delta = cp->deltaspace;
  203.  
  204.         for (i = 0; i <= CHAR_MAX; i++)
  205.                 delta[i] = p1;
  206.  
  207.         for (p = (unsigned char *)pat, i = p1; --i > 0;)
  208.                 delta[*p++] = i;
  209.  
  210.         cp->patlen = patlen;
  211.         return((char*) cp);
  212. }
  213.  
  214. static char *
  215. BoyerMooreExecute (text, textlen, compPtr, patLenP)
  216.         char     *text;
  217.         unsigned  textlen;
  218.         char     *compPtr;
  219.         unsigned *patLenP;
  220. {
  221.         register unsigned char *p, *t;
  222.         struct compiled_search_struct *csp = 
  223.             (struct compiled_search_struct*) compPtr;
  224.         register unsigned i, j, *delta = csp->deltaspace;
  225.         int p1;
  226.         char *pat;
  227.         unsigned patlen;
  228.  
  229.         *patLenP = p1 = patlen = csp->patlen;
  230.         /* code below fails (whenever i is unsigned) if pattern too long */
  231.         if (p1 > textlen)
  232.                 return (NULL);
  233.  
  234.         pat = (char *)csp + sizeof(struct compiled_search_struct);
  235.         /*
  236.          * From now on, we want patlen - 1.
  237.          * In the loop below, p points to the end of the pattern,
  238.          * t points to the end of the text to be tested against the
  239.          * pattern, and i counts the amount of text remaining, not
  240.          * including the part to be tested.
  241.          */
  242.         p1--;
  243.         p = (unsigned char *)pat + p1;
  244.         t = (unsigned char *)text + p1;
  245.         i = textlen - patlen;
  246.         for (;;) {
  247.                 if (*p == *t && 
  248.                     memcmp((p - p1), (t - p1), p1) == 0)
  249.                         return ((char *)t - p1);
  250.                 j = delta[*t];
  251.                 if (i < j)
  252.                         break;
  253.                 i -= j;
  254.                 t += j;
  255.         }
  256.         return (NULL);
  257. }
  258.  
  259.  
  260. /*
  261.  *-----------------------------------------------------------------------------
  262.  *
  263.  * Tcl_RegExpClean --
  264.  *     Free all resources associated with a regular expression info 
  265.  *     structure..
  266.  *
  267.  *-----------------------------------------------------------------------------
  268.  */
  269. void
  270. Tcl_RegExpClean (regExpPtr)
  271.     Tcl_regexp *regExpPtr;
  272. {
  273.     if (regExpPtr->progPtr != NULL)
  274.         ckfree ((char *) regExpPtr->progPtr);
  275.     if (regExpPtr->boyerMoorePtr != NULL)
  276.         ckfree ((char *) regExpPtr->boyerMoorePtr);
  277. }
  278.  
  279. /*
  280.  *-----------------------------------------------------------------------------
  281.  *
  282.  * FindNonRegExpSubStr
  283.  *     Find the largest substring that does not have any regular 
  284.  *     expression meta-characters and is not located within `[...]'.
  285.  *     If the regexp contains an or (|), zero is returned, as the 
  286.  *     Boyer-Moore optimization does not work, since there are actually
  287.  *     multiple patterns.  The real solution is to build the Boyer-Moore
  288.  *     into the regular expression code.
  289.  *-----------------------------------------------------------------------------
  290.  */
  291. static int
  292. FindNonRegExpSubStr (expression, subStrPtrPtr)
  293.     char  *expression;
  294.     char **subStrPtrPtr;
  295. {
  296.     register char *subStrPtr = NULL;
  297.     register char  subStrLen = 0;
  298.     register char *scanPtr   = expression;
  299.     register int   len;
  300.  
  301.     while (*scanPtr != '\0') {
  302.         len = strcspn (scanPtr, REXP_META);
  303.         /*
  304.          * If we are at a meta-character, by-pass till non-meta.  If we hit
  305.          * a `[' then by-pass the entire `[...]' range, but be careful, could
  306.          * have omitted `]'.  In a `|' is encountered (except in brackets),'
  307.          * we are through.
  308.          */
  309.         if (len == 0) {
  310.             scanPtr += strspn (scanPtr, REXP_META_NO_BRACKET_NO_OR);
  311.             if (*scanPtr == '|')
  312.                 return 0;
  313.             if (*scanPtr == '[') {
  314.                 scanPtr += strcspn (scanPtr, "]");
  315.                 if (*scanPtr == ']')
  316.                     scanPtr++;
  317.             }          
  318.         } else {
  319.             if (len > subStrLen) {
  320.                 subStrPtr = scanPtr;
  321.                 subStrLen = len;
  322.             }
  323.             scanPtr += len;
  324.         }
  325.     }
  326.     *subStrPtrPtr = subStrPtr;
  327.     return subStrLen;
  328. }
  329.  
  330. /*
  331.  *-----------------------------------------------------------------------------
  332.  *
  333.  * Tcl_RegExpCompile --
  334.  *     Compile a regular expression.
  335.  *
  336.  * Parameters:
  337.  *     o regExpPtr - Used to hold info on this regular expression.  If the
  338.  *       structure is being reused, it Tcl_RegExpClean should be called first.
  339.  *     o expression - Regular expression to compile.
  340.  *     o flags - The following flags are recognized:
  341.  *         o REXP_NO_CASE - Comparison will be regardless of case.
  342.  *         o REXP_BOTH_ALGORITHMS - If specified, a Boyer-Moore expression is 
  343.  *           compiled for the largest substring of the expression that does
  344.  *           not contain any meta-characters.  This is slows compiling, but
  345.  *           speeds up large searches.
  346.  *
  347.  * Results:
  348.  *     Standard TCL results.
  349.  *-----------------------------------------------------------------------------
  350.  */
  351. int
  352. Tcl_RegExpCompile (interp, regExpPtr, expression, flags)
  353.     Tcl_Interp  *interp;
  354.     Tcl_regexp  *regExpPtr;
  355.     char        *expression;
  356.     int          flags;
  357. {
  358.     char *expBuf;
  359.     int   anyMeta;
  360.  
  361.     if (*expression == '\0') {
  362.         Tcl_AppendResult (interp, "Null regular expression", (char *) NULL);
  363.         return TCL_ERROR;
  364.     }
  365.  
  366.     regExpPtr->progPtr = NULL;
  367.     regExpPtr->boyerMoorePtr = NULL;
  368.     regExpPtr->noCase = flags & REXP_NO_CASE;
  369.  
  370.     if (flags & REXP_NO_CASE) {
  371.         expBuf = ckalloc (strlen (expression) + 1);
  372.         Tcl_DownShift (expBuf, expression);
  373.     } else
  374.         expBuf = expression;
  375.  
  376.     anyMeta = strpbrk (expBuf, REXP_META) != NULL;
  377.  
  378.     /*
  379.      * If no meta-characters, use Boyer-Moore string matching only.
  380.      */
  381.     if ((!anyMeta) && (flags & REXP_BOTH_ALGORITHMS)) {
  382.         regExpPtr->boyerMoorePtr = BoyerMooreCompile (expBuf, strlen (expBuf));
  383.         goto okExitPoint;
  384.     }
  385.  
  386.     /*
  387.      * Build a Boyer-Moore on the largest non-meta substring, if requested,
  388.      * and the reg-exp does not contain a `|' (or).  If less that three
  389.      * characters in the string, don't use B-M, as it seems not optimal at
  390.      * this point.
  391.      */
  392.     if (flags & REXP_BOTH_ALGORITHMS) {
  393.         char *subStrPtr;
  394.         int   subStrLen;
  395.         
  396.         subStrLen = FindNonRegExpSubStr (expBuf, &subStrPtr);
  397.         if (subStrLen > 2)
  398.             regExpPtr->boyerMoorePtr = 
  399.                 BoyerMooreCompile (subStrPtr, subStrLen);
  400.     }
  401.     
  402.     /*
  403.      * Compile meta-character containing regular expression.
  404.      */
  405.     tclRegexpError = NULL;
  406.     regExpPtr->progPtr = TclRegComp (expBuf);
  407.     if (tclRegexpError != NULL) {
  408.         if (flags & REXP_NO_CASE)
  409.             ckfree (expBuf);
  410.         Tcl_AppendResult (interp, "error in regular expression: ", 
  411.                           tclRegexpError, (char *) NULL);
  412.         if (flags & REXP_NO_CASE)
  413.             ckfree (expBuf);
  414.         Tcl_RegExpClean (regExpPtr);
  415.     }
  416.   
  417. okExitPoint: 
  418.     if (flags & REXP_NO_CASE)
  419.         ckfree (expBuf);
  420.     return TCL_OK;
  421.  
  422. }
  423.  
  424. /*
  425.  *-----------------------------------------------------------------------------
  426.  *
  427.  * Tcl_RegExpExecute --
  428.  *     Execute a regular expression compiled with Boyer-Moore and/or 
  429.  *     regexp.
  430.  *
  431.  * Parameters:
  432.  *     o regExpPtr - Used to hold info on this regular expression.
  433.  *     o matchStrIn - String to match against the regular expression.
  434.  *     o matchStrLower - Optional lower case version of the string.  If
  435.  *       multiple no case matches are being done, time can be saved by
  436.  *       down shifting the string in advance.  NULL if not a no-case 
  437.  *       match or this procedure is to do the down shifting.
  438.  *     o subMatchInfo - A array of entries containing the indexs and
  439.  *       lengths of each submatch.  Teminated by an entry of -1, -1.
  440.  * Results:
  441.  *     TRUE if a match, FALSE if it does not match.
  442.  *
  443.  *-----------------------------------------------------------------------------
  444.  */
  445. int
  446. Tcl_RegExpExecute (interp, regExpPtr, matchStrIn, matchStrLower, subMatchInfo)
  447.     Tcl_Interp       *interp;
  448.     Tcl_regexp       *regExpPtr;
  449.     char             *matchStrIn;
  450.     char             *matchStrLower;
  451.     Tcl_SubMatchInfo  subMatchInfo;
  452. {
  453.     char   *matchStr;
  454.     int     result, idx;
  455.     regexp *progPtr;
  456.  
  457.     if (regExpPtr->noCase) {
  458.         if (matchStrLower == NULL) {
  459.             matchStr = ckalloc (strlen (matchStrIn) + 1);
  460.             Tcl_DownShift (matchStr, matchStrIn);
  461.         } else
  462.             matchStr = matchStrLower;
  463.     } else {
  464.         matchStr = matchStrIn;
  465.     }
  466.  
  467.     /*
  468.      * If a Boyer-Moore pattern has been compiled, use that algorithm to test
  469.      * against the text.  If that passes, then test with the regexp if we have
  470.      * it.
  471.      */
  472.     if (regExpPtr->boyerMoorePtr != NULL) {
  473.         char     *startPtr;
  474.         unsigned  matchLen;
  475.  
  476.         startPtr = BoyerMooreExecute (matchStr, strlen (matchStr), 
  477.                                       regExpPtr->boyerMoorePtr, &matchLen);
  478.         if (startPtr == NULL) {
  479.             result = FALSE;
  480.             goto exitPoint;
  481.         }
  482.         /* 
  483.          * If no regexp, its a match!
  484.          */
  485.         if (regExpPtr->progPtr == NULL) {
  486.             subMatchInfo [0].start = -1;
  487.             subMatchInfo [0].end = -1;
  488.             result = TRUE; 
  489.             goto exitPoint;
  490.         }
  491.     }
  492.     
  493.     /*
  494.      * Give it a go with full regular expressions
  495.      */
  496.     progPtr = regExpPtr->progPtr;
  497.     result = TclRegExec (progPtr, matchStr, matchStr);
  498.  
  499.     /*
  500.      * Return submatches if we found it.
  501.      */
  502.     if (result) {
  503.         for (idx = 1; idx < NSUBEXP; idx++) {
  504.             if (progPtr->startp [idx] == NULL)
  505.                 break;
  506.             subMatchInfo [idx - 1].start = progPtr->startp [idx] - matchStr;
  507.             subMatchInfo [idx - 1].end = progPtr->endp [idx] - matchStr - 1;
  508.         }
  509.         subMatchInfo [idx - 1].start = -1;
  510.         subMatchInfo [idx - 1].end = -1;
  511.     }
  512.  
  513.     /*
  514.      * Clean up and return status here.
  515.      */
  516. exitPoint:
  517.     if ((regExpPtr->noCase) && (matchStrLower == NULL))
  518.         ckfree (matchStr);
  519.     return result;
  520. }
  521.